package leetcode100

// TODO 滑动窗口 | 字符串处理 【-】 找到字符串中所有字母异位词
// TODO https://leetcode.cn/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-jia-shu-zu-ha-xi-by-j1zd8/

func findAnagrams(s string, p string) []int {
	// 滑动窗口+哈希
	if len(s) < len(p) {
		return nil
	}
	cntP, cntS := [26]int{}, [26]int{}
	ans := []int{}
	for i := range p {
		cntP[p[i]-'a']++
		cntS[s[i]-'a']++
	}
	if cntP == cntS {
		ans = append(ans, 0)
	}
	for i := len(p); i < len(s); i++ {
		cntS[s[i]-'a']++
		cntS[s[i-len(p)]-'a']--
		if cntS == cntP {
			ans = append(ans, i-len(p)+1)
		}
	}
	return ans
}
